/**
 * @type {string[][]}
 */
const paths = []; // 存储所有路径

/**
 * 查找图中从起点到终点的所有无环路径
 * @param {Record<string, string[]>} graph 图的邻接表表示 {A: ['B', 'C'], B: ['D'], ...}
 * @param {string} start 起点节点
 * @param {string} end 终点节点
 * @returns {string[][]} 所有无环路径的数组
 */
function findAllPaths(graph, start, end) {
  /**
   * @type {Set<string>}
   */
  const visited = new Set(); // 记录已访问节点
  /**
   * @type {string[]}
   */
  const currentPath = []; // 当前路径

  // 执行深度优先搜索
  dfs(start, visited, currentPath, paths, graph, end);

  return paths;
}

/**
 * 深度优先搜索辅助函数
 * @param {string} node 当前节点
 * @param {Set<string>} visited 已访问节点集合
 * @param {string[]} currentPath 当前路径
 * @param {string[][]} paths 结果路径集合
 * @param {Record<string, string[]>} graph 图
 * @param {string} end 目标节点
 */
function dfs(node, visited, currentPath, paths, graph, end) {
  // 标记当前节点为已访问
  visited.add(node);
  currentPath.push(node);

  // 如果到达目标节点，保存当前路径
  if (node === end) {
    paths.push([...currentPath]);
  } else {
    // 遍历所有邻居节点
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      // 只有当邻居未被访问时才继续搜索
      if (!visited.has(neighbor)) {
        dfs(neighbor, visited, currentPath, paths, graph, end);
      }
    }
  }

  // 回溯：移除当前节点，准备探索其他路径
  visited.delete(node);
  currentPath.pop();
}

// 示例用法
/**
 * @type {Record<string, string[]>}
 */
const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: ["F"],
  E: ["F"],
  F: [],
};

console.log(findAllPaths(graph, "A", "F"));
/*
输出:
[
  ["A", "B", "D", "F"],
  ["A", "B", "E", "F"],
  ["A", "C", "F"]
]
*/
